import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class test4 {

    public static int N, M;
    public static int[][] maze_1;
    public static int[][] maze_2;
    public static int[][] max1;
    public static int[][] max2;
    public static List<String> way = new ArrayList<>();


    public static void dp_fun(int x, int y, int target[][], int result[][]){
        result[x][y] = target[x][y];
        int max = 0;
        if(x > 0 && max < result[x-1][y])
            max = result[x-1][y];
        if(y > 0 && max < result[x][y-1])
            max = result[x][y-1];
        result[x][y] += max;
        if(x < N - 1)
            dp_fun(x+1, y, target, result);
        if(y < M - 1)
            dp_fun(x, y+1, target, result);
    }

    public static void wayAndclean(int x, int y){
        maze_1[x][y] = 0;
        if( x == 0)
            for (int i = y; i >= 0; i--)
            {
                if(i != y)
                    way.add("(" + x + ", " + i + ")");
                maze_1[x][i] = 0;
            }
        if (y == 0)
            for (int i = x; i >= 0; i--){
                if(i != x)
                    way.add("(" + i + ", " + y + ")");
                maze_1[i][y] = 0;
            }
        if(x >0 && y >0 && max1[x-1][y] > max1[x][y-1]){
            way.add("("+(x-1) + ", " + y + "）");
            maze_1[x-1][y] = 0;
            wayAndclean(x-1, y);
        }else if(x >0 && y > 0 && max1[x-1][y] < max1[x][y-1]){
            way.add("(" + x + ", " + (y-1) + ")");
            maze_1[x][y-1] = 0;
            wayAndclean(x, y-1);
        }
    }
    public static void wayAndclean_reserved(int x, int y){
        maze_1[N-x-1][M-y-1] = 0;
        if( x == 0)
            for (int i = y; i >= 0; i--)
            {
                if(i != y)
                    way.add("(" + (N-x-1) + ", " + (M-i-1) + ")");
                maze_1[N-x-1][M-i-1] = 0;
            }
        if (y == 0)
            for (int i = x; i >= 0; i--){
                if(i != x)
                    way.add("(" + (N-i-1) + ", " + (M-y-1) + ")");
                maze_1[N-i-1][M-y-1] = 0;
            }
        if(x >0 && y > 0 && max2[x-1][y] > max2[x][y-1]){
            way.add("("+(N-(x-1)-1) + ", " + (M-y-1) + "）");
            maze_1[N-(x-1)-1][M-y-1] = 0;
            wayAndclean_reserved(x-1, y);
        }else if(x > 0 && y > 0 && max2[x-1][y] < max2[x][y-1]){
            way.add("(" + (N-x-1) + ", " + (M-(y-1)-1) + ")");
            maze_1[N-x-1][M-(y-1)-1] = 0;
            wayAndclean_reserved(x, y-1);
        }
    }






    public static void main(String[] args) {
        while (true){
            Scanner sc = new Scanner(System.in);
            System.out.println("Please input N and M:(Input 'END' to STOP) ");
            way.clear();
            String str = sc.nextLine();
            if(str.equals("END"))
                break;
            else {
                String str1[]  = str.split(" ");
                N = Integer.parseInt(str1[0]);
                M = Integer.parseInt(str1[1]);
                if(N < 0 || M < 0)
                    System.out.println("Wrong number, please input once again.");
                else{
                    maze_1 = new int[N][M];
                    for (int i = 0; i < N; i++){
                        System.out.println("Please input the " + (int)(i+1) + " row");
                        String str2[] = sc.nextLine().split(" ");
                        for (int j =0; j < M; j++){
                            maze_1[i][j] = Integer.parseInt(str2[j]);
                        }
                    }
                }
                //这里调用算法逻辑的方法
                max1 = new int[N][M];
                dp_fun(0, 0, maze_1, max1);
                way.add("(" + (N-1) + ", " + (M-1) + ")" );
                wayAndclean(N-1, M-1);
                Collections.reverse(way);
                System.out.println("前往（" + (N-1) + ", " +(M-1) + ")的路径为:");
                for (int i = 0; i < way.size(); i++){
                    System.out.print(way.get(i));
                }
                System.out.println();
                way.clear();
                maze_2 = new int[N][M];
                for(int i = 0; i < N; i++) {
                    for (int j = 0; j < M; j++)
                        maze_2[i][j] = maze_1[N-i-1][M-j-1];
                }
                int sum1 = max1[N-1][M-1];
                max2 = new int[N][M];
                dp_fun(0, 0, maze_2, max2);
                wayAndclean_reserved(N-1 ,M-1);
                Collections.reverse(way);
                way.add("(0, 0)" );
                int sum2 = max2[N-1][M-1];
                System.out.println("前往（0, 0)的路径为:");
                for (int i = 0; i < way.size(); i++) {
                    System.out.print(way.get(i));
                }
                System.out.println();
                System.out.println("最大奖励数为: " + (sum1+sum2));


            }
        }
    }
}